package leetcode.easy.q121;

import leetcode.util.Utils;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class Q {
    public static void main(String[] args) {
        log.info("res:{}",new Solution3().maxProfit(Utils.toArray(7,1,5,3,6,4)));
        log.info("res:{}",new Solution2().maxProfit(Utils.toArray(7,1,5,3,6,4)));
        log.info("res:{}",new Solution1().maxProfit(Utils.toArray(7,1,5,3,6,4)));
    }
}

class Solution3 {
    /**
     * 动态规划，记录每天卖出时的最小买入
     **/
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int max = 0, diff = 0;
        for (int i = 1; i < prices.length; i++) {
            min = min > prices[i - 1] ? prices[i - 1] : min;
            if ((diff = prices[i] - min) > max) {
                max = diff;
            }
        }
        return max;
    }
}

class Solution2 {
    /**
     * 动态规划，记录每天卖出时的最小买入
     */
    public int maxProfit(int[] prices) {
        int[] min = new int[prices.length];
        min[0] = prices[0];
        int max = 0, diff = 0;
        for (int i = 1; i < prices.length; i++) {
            min[i] = Math.min(prices[i - 1], min[i - 1]);
            if ((diff = prices[i] - min[i]) > max) {
                max = diff;
            }
        }
        return max;
    }
}

class Solution1 {
    /**
     * 动态规划，记录每天的最大收益(可正可负)
     */
    public int maxProfit(int[] prices) {
        int[] profits = new int[prices.length];
        profits[0] = 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            profits[i] = Math.max(diff, profits[i - 1] + diff);
            if (profits[i] > max) {
                max = profits[i];
            }
        }
        return max;
    }

}